CSE 311: Homework 5 Part 2

Due: Friday, May 22nd by 6:00 PM

Instructions

Write up carefully argued solutions to the following problems. Each solution should be clear enough that it can explain (to someone who does not already understand the answer) why it works. However, you may use results from lecture, the reference sheets, and previous homework without proof.

You are required to submit your own solutions. You are allowed to discuss the homework with other students. However, the write up must clearly be your own, and moreover, you must be able to explain your solution at any time. We reserve ourselves the right to ask you to explain your work at any time in the course of this class.

You have a total of three late days during the quarter, but you can only use one late day on any one homework, giving an additional day on both parts. Please plan ahead.

Submit your solution via Gradescope. In particular:

• Each numbered task should be solved on its own page (or pages). Do not write your name on the individual pages. (Gradescope will handle that.)

• When you upload your pages, make sure each one is properly rotated. If not, you can use the Gradescope controls to turn them to the proper orientation.

• Follow the Gradescope prompt to link tasks to pages.

• You are not required to typeset your solution, but your submission must be legible. It is your responsibility to make sure solutions are readable — we will not grade unreadable write-ups.

Task 1 – Relatin’ Canes

For each of the relations below, determine whether or not it has each of the properties of reflexivity, symmetry, antisymmetry, and/or transitivity. If a relation has a property, simply say so without any further explanation. If a relation does not have a property, state a counterexample, but do not explain your counterexample further.

1. Define $R\subseteq \mathbb{Z}\times\mathbb{Z}$ by $(a,b) \in R$ iff $a + 2b$ is odd.

2. Define $S\subseteq \mathbb{N}\times\mathbb{N}$ by $(a,b) \in S$ iff $a \cdot b \geq 0$.

3. Let $A = \{k \in \mathbb{Z} : k < 0\}$ be the set of negative integers. Define $T\subseteq A \times A$ by $(a,b)\in T$ iff $a \times b < 0$

4. Let $B = \mathcal{P}(\mathbb{Z})$. Define $U \subseteq B\times B$ by $(X,Y)\in U$ iff $X\cup\mathbb{N}\subseteq Y\cap\mathbb{N}$. (Remember that $\mathbb{N}\subseteq\mathbb{Z}$.)

    Hint: What can be in $X$? What can’t be?

Task 2 – Better Get Proving

Let $R$ be a relation on a set $A$. Recall from lecture the definition of the composition of two relations:

$$R \circ R := \{ (a, b)\ |\ \mathbf{\exists c}\, ((a, \mathbf{c}) \in R \wedge (\mathbf{c}, b) \in R)\}$$

and “$R$ is transitive” iff $$\forall a \in A\, \forall b \in A\, \forall c \in A\, (((a, b) \in R \wedge (b, c) \in R) \to (a, c) \in R)$$

and “$R$ is antisymmetric” iff $$\forall a \in A\, \forall b \in A\, (((a, b) \in R \wedge (b, a) \in R) \to a = b)$$

The definition of antisymmetric is different from the one in the lecture, but it is equivalent. Using this definition can make the proof slightly easier.

 Now, consider the following claim:

  Given that $R$ is transitive and antisymmetric, it follows that $R \circ R$ is antisymmetric.

Write an English proof that the claim holds.

 Note: Even though we want you to write your proof directly in English, it must still look like the translation of a formal proof. In particular, you must include all steps that would be required of a formal proof, excepting only those that we have explicitly said are okay to skip in English proofs (e.g., Elim $\exists$).

Task 3 – Don’t Stop BelEven’

Let $\Sigma = \{0,1\}$, and consider the following language:

$$L = \left\{w\in\Sigma^*:\operatorname{\texttt{Even}}\big(\#_0(w)\big)\land\operatorname{\texttt{Even}}\big(\#_1(w)\big)\right\}$$

That is,

$L$ is the language consisting of all binary strings that have an even number of $0$’s and an even number of $1$’s.

1. Give a DFA that recognizes $L$. For each state, write a short description of the set of strings that end in that state.

2. Give a regular expression that matches $L$. Try to give it some thought before reading the hint¹ below!

3. Consider the following language

   $M$, which is a subset of $L$:

   $$M = \left\{w\in\Sigma^*:\operatorname{\texttt{Even}}\big(\#_0(w)\big)\land\operatorname{\texttt{Even}}\big(\#_1(w)\big)\land\#_0(w) = \#_1(w)\right\}$$

   $M$ is the language consisting of all binary strings that have an even number of $0$’s, an even number of $1$’s, and the same number of $0$’s and $1$’s. Give a CFG that generates $M$.

   If your grammar has more than one variable (also called a non-terminal symbol), for each variable, write a short description of the set of strings you expect it to generate.

Task 4 – Optional Practice Problems (Extra Credit)

The following problems are optional and do not need to be submitted. However, you may submit solutions and receive a small amount of extra credit for any 5 (of the 9) subparts, graded solely on completion. For the maximum extra credit score, at least 5 subparts should be submitted, including at least one subpart from each of the three sections.

1. For each of the following regular languages, construct a regular expression, an FSM, and a CFG.

   1. Nonempty strings over $\{0,1,2\}$ whose digit sums have the same parity as their last digit. That is, if the last digit is even, then the sum of the digits should be even, and if the last digit is odd, then the sum of the digits should be odd.

   2. Binary strings where the difference between the number of 0’s and the number of 1’s is even.

   3. Binary strings that do not contain the substring 00.

   4. Strings over $\{a, b\}$ in which every a is immediately followed by a b.

2. Construct CFGs for the following languages (which are not regular).

   1. $\{a^n b^m : n \leq m \leq 2n,\ n \geq 0\}$.

   2. $\{w \in \{0,1\}^* : w \text{ has strictly more \texttt{1}'s than \texttt{0}'s}\}$.

3. Let $R$ be a relation on an arbitrary set $A$.

   1. Prove: if $R$ is reflexive and transitive, then $R \circ R = R$. (How do you prove set equality?)

   2. Prove: if $R$ is symmetric, then $R \circ R$ is symmetric.

   3. Prove: if $R_1$ and $R_2$ are both equivalence relations on $A$, then $R_1 \cap R_2$ is also an equivalence relation on $A$.